package org.apache.commons.graph.connectivity

import org.apache.commons.graph.CommonsGraph.findConnectedComponent
import org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph
import org.apache.commons.graph.Graph
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledEdge
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.BaseLabeledWeightedEdge
import org.apache.commons.graph.model.UndirectedMutableGraph
import org.junit.Assert
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 */
class FindConnectedComponetTestCase {
    @Test
    fun testVerifyConnectedComponents() {
        val a = BaseLabeledVertex("A")

        val graph: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    addVertex(a)
                    addVertex(BaseLabeledVertex("B"))
                    addVertex(BaseLabeledVertex("C"))
                    addVertex(BaseLabeledVertex("D"))
                    addVertex(BaseLabeledVertex("E"))
                    addVertex(BaseLabeledVertex("F"))
                    addVertex(BaseLabeledVertex("G"))
                    addVertex(BaseLabeledVertex("H"))
                }
            })

        val c: Collection<List<BaseLabeledVertex>> = findConnectedComponent(graph).includingAllVertices().applyingMinimumSpanningTreeAlgorithm()

        Assert.assertNotNull(c)
        Assert.assertFalse(c.isEmpty())
        Assert.assertEquals(8, c.size.toLong())
    }

    @Test
    fun testVerifyConnectedComponents2() {
        val a = BaseLabeledVertex("A")

        val graph: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    addVertex(a)
                    val b = addVertex(BaseLabeledVertex("B"))
                    val c = addVertex(BaseLabeledVertex("C"))
                    val d = addVertex(BaseLabeledVertex("D"))
                    val e = addVertex(BaseLabeledVertex("E"))
                    val f = addVertex(BaseLabeledVertex("F"))
                    val g = addVertex(BaseLabeledVertex("G"))
                    val h = addVertex(BaseLabeledVertex("H"))

                    addEdge(BaseLabeledEdge("A -> F")).from(a).to(f)
                    addEdge(BaseLabeledEdge("A -> B")).from(a).to(b)
                    addEdge(BaseLabeledEdge("B -> F")).from(b).to(f)
                    addEdge(BaseLabeledEdge("C -> G")).from(c).to(g)
                    addEdge(BaseLabeledEdge("D -> G")).from(d).to(g)
                    addEdge(BaseLabeledEdge("E -> F")).from(e).to(f)
                    addEdge(BaseLabeledEdge("H -> C")).from(h).to(c)
                }
            })

        val c: Collection<List<BaseLabeledVertex>> =
            findConnectedComponent(graph).includingAllVertices().applyingMinimumSpanningTreeAlgorithm()

        Assert.assertNotNull(c)
        Assert.assertFalse(c.isEmpty())
        Assert.assertEquals(2, c.size.toLong())
    }

    @Test
    fun testVerifyConnectedComponents3() {
        val a = BaseLabeledVertex("A")

        val graph: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    addVertex(a)
                    val b = addVertex(BaseLabeledVertex("B"))
                    val c = addVertex(BaseLabeledVertex("C"))

                    addEdge(BaseLabeledEdge("A -> B")).from(a).to(b)
                    addEdge(BaseLabeledEdge("B -> C")).from(b).to(c)
                    addEdge(BaseLabeledEdge("C -> A")).from(c).to(a)
                }
            })

        val c: Collection<List<BaseLabeledVertex>> =
            findConnectedComponent(graph).includingAllVertices().applyingMinimumSpanningTreeAlgorithm()

        Assert.assertNotNull(c)
        Assert.assertFalse(c.isEmpty())
        Assert.assertEquals(1, c.size.toLong())
    }

    @Test
    fun testVerifyConnectedComponentsIncludingVertices() {
        val a = BaseLabeledVertex("A")

        val graph: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    addVertex(a)
                    val b = addVertex(BaseLabeledVertex("B"))
                    val c = addVertex(BaseLabeledVertex("C"))
                    val d = addVertex(BaseLabeledVertex("D"))
                    val e = addVertex(BaseLabeledVertex("E"))
                    val f = addVertex(BaseLabeledVertex("F"))
                    val g = addVertex(BaseLabeledVertex("G"))
                    val h = addVertex(BaseLabeledVertex("H"))

                    addEdge(BaseLabeledEdge("A -> F")).from(a).to(f)
                    addEdge(BaseLabeledEdge("A -> B")).from(a).to(b)
                    addEdge(BaseLabeledEdge("B -> F")).from(b).to(f)
                    addEdge(BaseLabeledEdge("C -> G")).from(c).to(g)
                    addEdge(BaseLabeledEdge("D -> G")).from(d).to(g)
                    addEdge(BaseLabeledEdge("E -> F")).from(e).to(f)
                    addEdge(BaseLabeledEdge("H -> C")).from(h).to(c)
                }
            })

        val coll: Collection<List<BaseLabeledVertex>> =
            findConnectedComponent(graph).includingVertices(a).applyingMinimumSpanningTreeAlgorithm()

        Assert.assertNotNull(coll)
        Assert.assertFalse(coll.isEmpty())
        Assert.assertEquals(1, coll.size.toLong())
    }

    @Test
    fun testVerifyConnectedComponentsIncludingVertices2() {
        val a = BaseLabeledVertex("A")
        val e = BaseLabeledVertex("E")

        val graph: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    addVertex(a)
                    addVertex(BaseLabeledVertex("B"))
                    addVertex(BaseLabeledVertex("C"))
                    addVertex(BaseLabeledVertex("D"))
                    addVertex(e)
                    addVertex(BaseLabeledVertex("F"))
                    addVertex(BaseLabeledVertex("G"))
                    addVertex(BaseLabeledVertex("H"))
                }
            })

        val coll: Collection<List<BaseLabeledVertex>> =
            findConnectedComponent(graph).includingVertices(a, e).applyingMinimumSpanningTreeAlgorithm()

        Assert.assertNotNull(coll)
        Assert.assertFalse(coll.isEmpty())
        Assert.assertEquals(2, coll.size.toLong())
    }

    @Test
    fun testVerifyEmptyGraph() {
        val graph =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()

        val c: Collection<List<BaseLabeledVertex>> =
            findConnectedComponent(graph).includingAllVertices().applyingMinimumSpanningTreeAlgorithm()
        Assert.assertNotNull(c)
        Assert.assertEquals(0, c.size.toLong())
    }

    @Test
    fun testVerifyNullVerticesGraph() {
        val graph: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    addVertex(BaseLabeledVertex("B"))
                    addVertex(BaseLabeledVertex("C"))
                }
            })
        val c: Collection<List<BaseLabeledVertex>> =
            findConnectedComponent(graph).includingVertices().applyingMinimumSpanningTreeAlgorithm()
        Assert.assertNotNull(c)
        Assert.assertEquals(0, c.size.toLong())
    }

//    @Test(expected = NullPointerException::class)
//    fun verifyNullGraph() {
//        findConnectedComponent(null as Graph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?).includingAllVertices()
//            .applyingMinimumSpanningTreeAlgorithm()
//    }
}
